#define _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <vector>
//using namespace std;
//int gcd(int m, int n)
//{
//	// 辗转相除->m = n, n = m % n
//	return n == 0 ? m : gcd(n, m % n);
//}
//
//int bin_gcd(int m, int n)
//{
//	// 结束条件
//	if (m == n) return m;
//	if (m < n) return bin_gcd(n, m);
//
//	// 递归条件
//	if (m % 2 == 0)
//	{
//		if (n % 2 == 0) return 2 * bin_gcd(m / 2, n / 2);
//		else return bin_gcd(m / 2, n);
//	}
//	else {
//		if (n % 2 == 0) return bin_gcd(m, n / 2);
//		else return bin_gcd(n, m - n);
//	}
//}
//
//int gcd_iter(int m, int n) 
//{
//	while (n != 0) 
//	{
//		int temp = n;
//		n = m % n;
//		m = temp;
//	}
//	return m;
//}
//
//void test1()
//{
//	int m, n;
//	cin >> m >> n;
//	int ans = gcd(m, n);
//	cout << ans << endl;
//
//	int ans1 = bin_gcd(m, n);
//	cout << ans1 << endl;
//
//	int ans2 = gcd_iter(m, n);
//	cout << ans2 << endl;
//}
//
//bool isSubsetSum(vector<int>& nums, int n, int target) 
//{
//	// 递归结束条件
//	if (target == 0) return true;
//	if (n == 0) return false;
//
//	// 当前数比target大，直接跳过
//	if (nums[n - 1] > target)
//		return isSubsetSum(nums, n - 1, target);
//
//	// 二选一
//	return isSubsetSum(nums, n - 1, target - nums[n - 1]) ||
//		isSubsetSum(nums, n - 1, target);
//}
//
//void testSubset() 
//{
//	int target, n;
//	cin >> n;
//	vector<int> nums(n);
//	for (int i = 0; i < n; ++i)
//		nums[i] = i;
//	cin >> target;
//	cout << (isSubsetSum(nums, n, target) ? "YES" : "NO") << endl;
//}
//
//int main() 
//{
//	testSubset();
//	return 0;
//}


#include <iostream>
#include <vector>
#include <numeric>  // 用于 accumulate
#include <algorithm>  // 用于 reverse
using namespace std;

// 递归解法：返回是否存在解及选中的数字
pair<bool, vector<int>> isSubsetSumWithSelection(vector<int>& nums, int n, int target) {
    if (target == 0) return { true, {} };
    if (n == 0) return { false, {} };

    if (nums[n - 1] > target) {
        return isSubsetSumWithSelection(nums, n - 1, target);
    }

    // 不包含当前数字的情况
    // 使用传统方式代替 auto [found, selected]
    auto result1 = isSubsetSumWithSelection(nums, n - 1, target);
    bool found1 = result1.first;
    vector<int> selected1 = result1.second;
    if (found1) {
        return { true, selected1 };
    }

    // 包含当前数字的情况
    // 使用传统方式代替 auto [found, selected]
    auto result2 = isSubsetSumWithSelection(nums, n - 1, target - nums[n - 1]);
    bool found2 = result2.first;
    vector<int> selected2 = result2.second;
    if (found2) {
        selected2.push_back(nums[n - 1]);
        return { true, selected2 };
    }

    return { false, {} };
}

// DP解法：返回是否存在解及选中的数字
pair<bool, vector<int>> subsetSumDP(vector<int>& nums, int target) {
    int n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));

    // 初始化：空集的和为0
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true;
    }

    // DP填表
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= target; ++j) {
            if (nums[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            }
            else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    // 如果没有解，直接返回
    if (!dp[n][target]) {
        return { false, {} };
    }

    // 回溯找选中的数字
    vector<int> selected;
    int i = n, j = target;
    while (i > 0 && j > 0) {
        if (dp[i][j] && !dp[i - 1][j]) {  // 当前数字被选中
            selected.push_back(nums[i - 1]);
            j -= nums[i - 1];
        }
        i--;
    }

    reverse(selected.begin(), selected.end());
    return { true, selected };
}

// 测试递归解法
void testSubsetWithSelection() {
    int n, m;
    cout << "输入数字个数: ";
    cin >> n;
    vector<int> nums(n);
    cout << "输入" << n << "个数字: ";
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    cout << "输入目标和: ";
    cin >> m;

    // 使用传统方式代替 auto [found, selected]
    auto result = isSubsetSumWithSelection(nums, n, m);
    bool found = result.first;
    vector<int> selected = result.second;

    if (found) {
        cout << "YES\n选中的数字: ";
        for (int num : selected) {
            cout << num << " ";
        }
        cout << endl;
        cout << "验证和: " << accumulate(selected.begin(), selected.end(), 0) << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

// 测试DP解法
void testSubsetDP() {
    int n, m;
    cout << "输入数字个数: ";
    cin >> n;
    vector<int> nums(n);
    cout << "输入" << n << "个数字: ";
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    cout << "输入目标和: ";
    cin >> m;

    // 使用传统方式代替 auto [found, selected]
    auto result = isSubsetSumWithSelection(nums, n, m);
    bool found = result.first;
    vector<int> selected = result.second;

    if (found) {
        cout << "YES\n选中的数字: ";
        for (int num : selected) {
            cout << num << " ";
        }
        cout << endl;
        cout << "验证和: " << accumulate(selected.begin(), selected.end(), 0) << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

int main() {
    cout << "=== 递归解法 ===" << endl;
    testSubsetWithSelection();

    cout << "\n=== DP解法 ===" << endl;
    testSubsetDP();

    return 0;
}